/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class deleteOperationForTwoStrings {    
	public static int minDistance(String word1, String word2) {
	    int len1 = word1.length(), len2 = word2.length();
	    if (len1 == 0) return len2;
	    if (len2 == 0) return len1;
	    // dp[i][j] stands for distance of first i chars of word1 and first j chars of word2
	    int[][] dp = new int[len1 + 1][len2 + 1];
	    for (int i = 0; i <= len1; i++)
	        dp[i][0] = i;
	    for (int j = 0; j <= len2; j++)
	        dp[0][j] = j;
	        
	    for (int i = 1; i <= len1; i++) {
	        for (int j = 1; j <= len2; j++) {
	            if (word1.charAt(i - 1) == word2.charAt(j - 1))
	                dp[i][j] = dp[i - 1][j - 1];
	            else
	                dp[i][j] = Math.min((dp[i - 1][j] + 1), dp[i][j - 1] + 1);
	            System.out.println((dp[i-1][j]+1)+"   "+(dp[i][j-1]+1)+"  "+(dp[i-1][j-1]+2));
	        }
	    }
	    
	    return dp[len1][len2];
	}
	
//    public static int minDistance(String word1, String word2) {
//        int len1=word1.length();
//        int len2=word2.length();
//        if(len1==0||len2==0){
//    		return len1+len2;
//    	}
//        int dp[][]=new int[len1][len2];
//        for (int i = 0; i < len1; i++) {
//			for (int j = 0; j < len2; j++) {
//				if(word1.charAt(i)==word2.charAt(j)){
//					if(i==0||j==0){
//						dp[i][j]=1;
//					}else {
//						dp[i][j]=dp[i-1][j-1]+1;
//					}
//				}else {
//					dp[i][j]=Math.max(i==0?0:dp[i-1][j], j==0?0:dp[i][j-1]);
//				}
//			}
//		}
//        return len1+len2-2*dp[len1-1][len2-1];
//    }
	public static void main(String[] args) {
		System.out.println(minDistance("sea", "eat"));
	}
}
